import math

class Node:
    name = " "
    x = 0
    y = 0
    depth = 0;

    def __init__(self,name,x,y):
        self.name = name
        self.x = x
        self.y = y
        

class Link:
    Distance = 0.0
    StartCity = ' '
    EndCity = ' '

    def __init__(self,StartCity,EndCity,Distance):
        self.StartCity = StartCity
        self.EndCity = EndCity
        self.Distance = Distance


class Graph:
    NodeList = []
    LinkList = []
    


    def NodeProcess(self,dataLine):
        mylist = []
        mylist = dataLine[:-1].split(";")
        print(mylist)
        n = Node(mylist[0],mylist[1],mylist[2])
        self.NodeList.append(n)

    def RoadProcess(self,dataline):
         mylist = []
         mylist = dataline[:-1].split(";")
         searchlist1 = []
         searchlist1.append(self.SearchX(mylist[0]))
         searchlist1.append(self.SearchY(mylist[0]))
         searchlist2 = []
         searchlist2.append(self.SearchX(mylist[1]))
         searchlist2.append(self.SearchY(mylist[1]))
         distance = self.CalculateDistance(int(searchlist1[0]),int(searchlist1[1]),int(searchlist2[0]),int(searchlist2[1]))
         l = Link(mylist[0],mylist[1],distance)
         print(mylist[0],mylist[1],distance);
         self.LinkList.append(l)



    def ReadLocations(self,fileName):
        dataFile = open(fileName)
        for dataLine in dataFile.readlines():
            self.NodeProcess(dataLine)
        dataFile.close()
        del dataFile

    def ReadRoads(self,fileName):
        dataFile = open(fileName)
        for dataLine in dataFile.readlines():
            self.RoadProcess(dataLine)
        dataFile.close()
        del dataFile
    
    def CalculateDistance(self,x1,y1,x2,y2):
        xtot = x2 - x1
        ytot = y2 - y1
        Distance = math.sqrt((xtot ** 2) + (ytot ** 2))
        return Distance

    def SearchX(self,Cityname):
        for node in self.NodeList:
            if(node.name == Cityname):
                return node.x
   
    def SearchY(self,Cityname):
        for node in self.NodeList:
            if(node.name == Cityname):
                return node.y



    def IterativeDeependingSearch(self):

        #StartCity = ""
        #GoalCity = ""
        #input_var = input("Travel from: ")
        #StartCity = input_var
        #input_var = input("Travel to: ")
        #GoalCity = input_var

        StartCity = "Ingolstadt"
        GoalCity = "Neuburg"

        result = False
        depth = 0

        for depth in range(0,1000000):
            result = self.DepthLimitedSearch(StartCity,GoalCity,depth)
            depth = depth + 1
            if(result != -1):
                print(result)
                return result

        


    def DepthLimitedSearch(self,City,GoalCity,depth):
        Frontier = []
        Path = []
        Frontier.append([City])

        while(len(Frontier) != 0): 

            #Path = Frontier.pop(0) #assignment b
            Path = Frontier.pop(self.ChooseNode(Frontier,GoalCity))
            end = Path[-1]
           
            if(end == GoalCity):
                return Path

            if(len(Path) < depth):
                for x in self.LinkList:
                    if( (x.StartCity == end) and (x.StartCity != x.EndCity)):
                        Frontier.insert(0,Path + [x.EndCity])
        return -1

    def ChooseNode(self,Frontier,GoalCity):
        Heuristic = []
        for x in Frontier:
            end = x[-1]
            for y in self.NodeList:
                if (end == y.name):
                    for goal in self.NodeList:
                        if(GoalCity == goal.name):
                            H = self.CalculateDistance(int(y.x),int(y.y),int(goal.x),int(goal.y))
                            Heuristic.append(H)
        WhichToChoose = Heuristic.index(min(Heuristic))
        return WhichToChoose
        





                 
          



    
# 
#    def ChooseNode(self, Frontier, GoalState):
#        for x in Frontier:
#            while(len(Frontier) != 0): 
#                Path = Frontier.pop(x) 
#                end = Path[-1]
#           
#               if(end == GoalCity):
#                    return Path
#
#                if(len(Path) < depth):
#                    for x in self.LinkList:
#                        if( (x.StartCity == end) and (x.StartCity != x.EndCity)):
#                            Frontier.insert(0,Path + [x.EndCity])
#        return -1 


g = Graph()
g.ReadLocations("locations.csv")
g.ReadRoads("roads-1.csv")
g.IterativeDeependingSearch()
print(g.CalculateDistance(584,273,642,451))
print(g.CalculateDistance(483,384,642,451))